package Algorithm.Dp;

import java.util.Arrays;

//https://leetcode-cn.com/problems/cat-and-mouse/
//913. 猫和老鼠
public class Leetcode913_notice_猫和老鼠 {

    /**
     * 这个博弈类的题第一次遇到， 官方题解有提到这种博弈类的题通常可以用 DP 来解决
     */
    class Solution {
        static final int MOUSE_WIN = 1;
        static final int CAT_WIN = 2;
        static final int DRAW = 0;

        int[][] graph;
        int n ;
        int[][][] dp;

        public int catMouseGame(int[][] graph) {
            this.graph = graph;
            this.n = graph.length;
            dp = new int[n][n][2*n];
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    Arrays.fill(dp[i][j], -1);
                }
            }

            return getResult(1, 2, 0);
        }

        public int getResult(int mouse, int cat, int turns){
            if (turns == n * 2) {
                return DRAW;
            }
            if (dp[mouse][cat][turns] < 0) {
                if (mouse == 0) {
                    dp[mouse][cat][turns] = MOUSE_WIN;
                } else if (cat == mouse) {
                    dp[mouse][cat][turns] = CAT_WIN;
                } else {
                    getNextResult(mouse, cat, turns);
                }
            }
            return dp[mouse][cat][turns];
        }

        public void getNextResult(int mouse, int cat, int turns){
            int curMove = turns % 2 == 0 ? mouse : cat;
            int defaultResult = curMove == mouse ? CAT_WIN : MOUSE_WIN;
            int result = defaultResult;
            int[] nodes = graph[curMove];
            for(int next : nodes){
                if(curMove == cat && next == 0){
                    continue;
                }

                int nextMouse = curMove == mouse ? next : mouse;
                int nextCat = curMove == cat ? next : cat;

                int nextResult = getResult(nextMouse, nextCat, turns + 1);

                if(nextResult != defaultResult){
                    result = nextResult;
                    if(result != DRAW){
                        break;
                    }
                }
            }

            dp[mouse][cat][turns] = result;
        }

    }
}
